package com.hyb.algorithm.data.struct.tree;

import com.alibaba.fastjson.JSONObject;

import java.util.*;

/**
 *  94、二叉树的中序遍历
 *  https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
 *
 *  方法二：迭代
 * 思路与算法
 *
 * 方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。
 *
 * 作者：力扣官方题解
 * 链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author: ybhu
 * @create: 2023/12/25 00:05
 */
public class InorderTraversal {


    public static void main(String[] args) {

        TreeNode treeNode=new TreeNode(1);

        treeNode.left=new TreeNode(2);

        treeNode.left.left=new TreeNode(4);
        treeNode.left.right=new TreeNode(5);
        treeNode.right=new TreeNode(3);
        treeNode.right.left=new TreeNode(6);


        List<Integer> list=  new InorderTraversal().inorderTraversal(treeNode);

        System.out.println(JSONObject.toJSON(list));

    }

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new ArrayDeque<>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

}
